package com.zklh.leetcode.structure.other;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 寻找数据流的中位数算法实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/7/24 11:44
 */
public class MedianFinder {

    private PriorityQueue<Integer> small;
    private PriorityQueue<Integer> large;


    public MedianFinder() {
        small = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        large = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // 放在small中
        if (small.size() < large.size()) {
            large.offer(num);
            small.add(large.poll());
        } else {
           small.add(num);
           large.add(small.poll());
        }
    }


    public double getMedian() {
        if (large.size() > 0) {
            return small.size() == large.size()  ?(small.peek()+large.peek())*1.0D / 2 : large.peek();
        } else {
            return 0D;
        }

    }


    public static void main(String[] args) {
        MedianFinder finder = new MedianFinder();
        finder.addNum(1);
        finder.addNum(2);
        System.out.println(finder.getMedian());
        finder.addNum(3);
        System.out.println(finder.getMedian());

    }

}
